/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和
 */

// 2. 排序+左右指针
// @lc code=start
func threeSum(nums []int) (ans [][]int) {
	sort.Ints(nums)

	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 || (i > 0 && nums[i] == nums[i-1]) {
			continue
		}

		left, right := i+1, len(nums)-1
		for left < right {
			if nums[i]+nums[left]+nums[right] == 0 {
				ans = append(ans, []int{nums[i], nums[left], nums[right]})
				for left++; left < right && nums[left] == nums[left-1]; left++ {
				}
			} else if nums[i]+nums[left]+nums[right] > 0 {
				for right--; left < right && nums[right] == nums[right+1]; right-- {
				}
			} else {
				for left++; left < right && nums[left] == nums[left-1]; left++ {
				}
			}
		}
	}

	return
}

// @lc code=end

// 1-2. 排序+暴力+去重 = 超时
// @lc code=start
func threeSum(nums []int) (ans [][]int) {

	sort.Ints(nums)

	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 || (len(ans) > 0 && ans[len(ans)-1][0] == nums[i]) {
			continue
		}

		for j := i + 1; j < len(nums)-1; j++ {
			if (nums[i]+nums[j] > 0) || (len(ans) > 0 && ans[len(ans)-1][0] == nums[i] && ans[len(ans)-1][1] == nums[j]) {
				continue
			}

			for k := j + 1; k < len(nums); k++ {
				if len(ans) > 0 && ans[len(ans)-1][0] == nums[i] && ans[len(ans)-1][1] == nums[j] && ans[len(ans)-1][2] == nums[k] {
					continue
				}

				if nums[i]+nums[j]+nums[k] == 0 {
					ans = append(ans, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}
	return
}

// @lc code=end

// 1-1. 暴力枚举，有重复，用例不通过
// @lc code=start
func threeSum(nums []int) (ans [][]int) {
	for i := 0; i < len(nums)-2; i++ {
		for j := i + 1; j < len(nums)-1; j++ {
			for k := j + 1; k < len(nums); k++ {
				if nums[i]+nums[j]+nums[k] == 0 {
					ans = append(ans, []int{nums[i], nums[j], nums[k]})
				}
			}
		}
	}
	return
}

// @lc code=end

